﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0063_BackspaceCompare : IAlgorithm
    {
        // 844. 比较含退格的字符串

        // 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
        // 如果相等，返回 true ；否则，返回 false 。
        // 注意：如果对空文本输入退格字符，文本继续为空。

        // 提示：
        //  1 <= s.length, t.length <= 200
        //  s 和 t 只含有小写字母以及字符 '#'

        // 进阶：
        //  你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

        public void Test()
        {
            // 算法参数定义
            string s = "a##abc##c", t = "ad#c";
            // 算法执行与打印
            Console.WriteLine(BackspaceCompare(s, t));
        }

        // 算法
        public bool BackspaceCompare(string s, string t)
        {
            int i = s.Length - 1, j = t.Length - 1;
            while (i >= 0 || j >= 0)
            {
                i = SkipIndex(s, i);
                j = SkipIndex(t, j);
                // 都有字符时，对应索引字符不一致 或 一个字符串有字符，另一个字符串没有字符 返回false
                if ((i >= 0 && j >= 0 && s[i] != t[j]) || (i >= 0 && j < 0) || (i < 0 && j >= 0))
                    return false;
                i--;
                j--;
            }
            return true;
        }
        private int SkipIndex(string str, int i)
        {
            // 需要退格的次数
            int count = 0;
            // 每次退格，有效值在该索引后两位，所以增加两次需退格数次
            if (i >= 0 && str[i] == '#')
                count += 2;
            while (i >= 0 && count > 0)
            {
                // 退一格
                i--;
                count--;
                // 说明对空白进行退格，此时直接退出即可
                if (i < 0)
                    break;
                // 如果需退格，则累加两次需退格次数
                if (str[i] == '#')
                    count += 2;
            }
            return i;
        }
        // 简化
        private int SkipIndex1(string str, int i)
        {
            int count = 0;
            while (i >= 0)
            {
                // 如果退格，则需要累计一次退格
                if (str[i] == '#')
                    count++; //count = count + 2 - 1;
                // 如果不退格，则成功退格一次
                else
                    count--;
                // 
                if (count < 0)
                    break;
                else
                    i--;
            }
            return i;
        }

        public bool BackspaceCompare1(string s, string t)
        {
            int i = s.Length - 1, j = t.Length - 1;
            int skipS = 0, skipT = 0;
            while (i >= 0 || j >= 0)
            {
                while (i >= 0)
                    if (s[i] == '#')
                    {
                        skipS++;
                        i--;
                    }
                    else if (skipS > 0)
                    {
                        skipS--;
                        i--;
                    }
                    else
                        break;
                while (j >= 0)
                    if (t[j] == '#')
                    {
                        skipT++;
                        j--;
                    }
                    else if (skipT > 0)
                    {
                        skipT--;
                        j--;
                    }
                    else
                        break;
                if (i >= 0 && j >= 0)
                    if (s[i] != t[j])
                        return false;
                    else
                    if (i >= 0 || j >= 0)
                        return false;
                i--;
                j--;
            }
            return true;
        }
    }
}
